package ink.lovejinhu.leetcode;

import ink.lovejinhu.common.TreeNode;

/**
 * @author jinhu
 * created 2021-07-23 16:13
 */
public class Solution_0543 {
    /**
     * @param root
     * @return
     */
    public int diameterOfBinaryTree(TreeNode root) {
        dfsMax(root);
        return max - 1;
    }

    public int max = Integer.MIN_VALUE;

    public void dfsMax(TreeNode root) {
        if (root == null) return;
        if ((maxDepth(root.left) + maxDepth(root.right) + 1) > max) max = maxDepth(root);
        dfsMax(root.right);
        dfsMax(root.left);
    }

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int right = maxDepth(root.right);
        int left = maxDepth(root.left);
        return Math.max(right, left) + 1;
    }
}
